package algorithm.recursionAndbacktrack.p93;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 93. 复原 IP 地址
 */
public class Solution3 {
    public List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        restoreIpAddresses(s, new ArrayDeque<>(), ips);
        return ips;
    }


    private void restoreIpAddresses(String str, ArrayDeque<Integer> nums, List<String> ips) {
        // 满了4个数字，就返回
        if (nums.size() == 4) {
            if (str.length() == 0) { // 字符没有剩余，表示一个合法的ip
                Iterator<Integer> iterator = nums.iterator();
                StringBuilder sb = new StringBuilder("" + iterator.next());
                while (iterator.hasNext()) {
                    sb.append("." + iterator.next());
                }
                ips.add(sb.toString());
            }
            return;
        }

        for (int i = 1; i <= 3 && str.length() >= i; i++) {
            String num_str = str.substring(0, i);
            Integer num = Integer.parseInt(num_str);
            if (num_str.equals("0") || (!num_str.startsWith("0") && num < 256)) {
                nums.addLast(num);
                restoreIpAddresses(str.substring(i), nums, ips);
                nums.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        // System.out.println(new Solution3().restoreIpAddresses("25525511135"));
        // System.out.println(new Solution3().restoreIpAddresses("0000"));
        System.out.println(new Solution3().restoreIpAddresses("101023"));
    }
}